Algorithmes de type homotopiques pour la minimisation des moindres carrés régularisés par la "norme" $\ell_0$

National audienceCette communication concerne la conception d'algorithmes d'approximation parcimonieuse pour les problèmes inverses mal conditionnés. Les algorithmes heuristiques proposés sont conçus pour minimiser des critères mixtes 2-0 du type min_x J (x; λ) = || y − Ax ||^2 + λ || x ||_0. Ce sont des algorithmes gloutons " bidirectionnels " définis en tant qu'extensions d'Orthogonal Least Squares (OLS). Leur développement est motivé par le très bon comportement empirique d'OLS et de ses versions dérivées lorsque le dictionnaire A est une matrice mal conditionnée. Nous présentons dans un premier temps l'algorithme Single Best Replacement (SBR) pour minimiser J (x; λ) à λ fixé [1], en mettant en avant ses propriétés de convergence. Nous proposons ensuite deux algorithmes permettant de minimiser J pour un continuum de valeurs de λ, ce qui conduit à estimer le chemin de régularisation L0 [2]. Ces algorithmes sont inspirés de l'algorithme d'homotopie pour la régularisation L1 [3, 4] et exploitent le caractère constant par morceaux du chemin de régularisation L0. Continuation Single Best Replacement (CSBR) est basé sur des appels à SBR pour des valeurs décroissantes de λ, calculées de manièere adaptative. L'algorithme plus sophistiqué L0-regularization Path Descent (L0-PD) effectue une reconstruction (sous-optimale) du chemin de régularisation en maintenant (i) une liste de supports candidats pour des valeurs décroissantes de λ; et (ii) une liste de valeurs critiques de λ autour desquelles la solution change. Les simulations numériques montrent l'efficacité des deux algorithmes pour des problèmes inverses difficiles comme la déconvolution impulsionnelle par un filtre passe-bas. Nous montrons finalement que les algorithmes proposés peuvent être avantageusement couplés avec des méthodes de sélection d'ordre comme le MDL (Minimum Description Length) afin de sélectionner automatiquement l'une des solutions parcimonieuses obtenues